package cs561.hao; 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Vector;
/*
class treeNode {
	//public int[] point = new int[5];
	public int indexInParent;//cost from root to this point
	public boolean root;
	public boolean leaf;
	public int x;//k
	public int y;
	public int vector_i;
	public int vector_j;//k-1
	public int g;
	public int h;
	boolean altRoot;
	public ArrayList<treeNode> childrenList = new ArrayList<treeNode>();//why not just one child, no grand child?
	public treeNode parent = null;
	
	public void addChild(treeNode child) {
		child.parent = this;
		child.root = false;
		child.leaf = true;
		child.indexInParent = childrenList.size();
		child.g = this.g + 1;
		childrenList.add(child);
		this.leaf =false;		
	}	
}*/


public class Search {
	
	public int[][]readFile(String file)
	{
		int width = 0;
		int height = 0;
		int[][]points = null;
		int pointType = -1;
		
		try {
			FileReader fr = new FileReader(file);
			BufferedReader br = new BufferedReader(fr);	
			int lineNum = 0;
		
			try {
				while((br.ready()) && (lineNum < 2))
				{					
					String line = br.readLine();
					if (lineNum == 0)
					{
						String[] str = line.split(" ");
						width = Integer.parseInt(str[1]);
					}
					else if (lineNum == 1)
					{
						String[] str = line.split(" ");
						height = Integer.parseInt(str[1]);
					}
					lineNum++;
				}				
				
				points = new int[height][width];
				leastG = new int[height][width];
				
				while(width/factor>0)
					factor = factor * 10;
				
				for(int i = 0; i < height; i++)
				{
					for(int j = 0; j < width; j++)
					{
						if(br.ready())
						{
							pointType = br.read();
							//System.out.println("pointType: " + pointType);
							switch(pointType) 
							{
								case 35: points[i][j] = -1;//#
										 break;
								case 32: points[i][j] = 1;//' '
										 break;
								case 83: points[i][j] = 2;//S
										 break;
								case 65: points[i][j] = 3;//A
										 break;
								case 70: points[i][j] = 4;//F	
										 break;
								default: System.out.println("Invalid input.");
										 System.exit(-1);
										 break;
							}
							//System.out.println("Read i = " + i + ", j = " + j + ", " + points[i][j]);
						}
					}
					br.skip(1);//the last character of the line is \n, so skip
				}	
				
			} catch (IOException e) {
				e.printStackTrace();
			}
		
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}	
		
		return points;
	}
	
	public void writePoints(int width, int height, int points[][])
	{
		
		try {
			FileWriter fw = new FileWriter("e:/test/racetrack_point.txt");
			BufferedWriter bw = new BufferedWriter(fw);
			for(int i = 0; i < height; i++)
			{
				for(int j = 0; j < width; j++)
				{
					//System.out.println("Write i = " + i + ", j = " + j + ", " + points[i][j]);
					switch(points[i][j])
					{
						case -1:bw.write('#');
								break;
						case  1:bw.write(' ');
								break;
						case  2:bw.write('S');
								break;
						case  3:bw.write('A');
								break;
						case  4:bw.write('F');
								break;
					}
					
				}
				bw.newLine();
			}
			bw.flush();
			bw.close();
			
		} catch (IOException e1) {
			e1.printStackTrace();
		}
	}
	
	public ArrayList<int[]> heuristic(ArrayList<int[]> _roadCells, ArrayList<int[]> _finishCells)// get the h of roadCell, ok
	{
		
		int[] tempFinishCell = null;
		double distance = -1; // straight line distance
		double minDistance = -1;
		ArrayList<Double> tempDistanceList = new ArrayList<Double>();
		for(int i = 0; i < _roadCells.size(); i++)
		{
			int[] tempRoadCell = new int[5];
			
			tempRoadCell = _roadCells.get(i).clone();//xk yk h ik-1 jk-1
			tempDistanceList.clear();
			for(int j = 0; j < _finishCells.size(); j++)
			{
				//tempFinishCell = new int[2];
				tempFinishCell = _finishCells.get(j).clone();				
				distance = Math.sqrt(Math.pow((tempRoadCell[0] - tempFinishCell[0]), 2) + Math.pow((tempRoadCell[1] - tempFinishCell[1]), 2));
				//System.out.println("Point " + i + ", distance " + j + " = " + distance);
				tempDistanceList.add(distance);
				
			}
			
			minDistance = tempDistanceList.get(0);//because only find min, no need to sort.
			//System.out.println("Point " + i + ", tempDistanceList distance 0 = " + tempDistanceList.get(0));
			for(int k = 1; k < tempDistanceList.size(); k++)
			{
				//System.out.println("Point " + i + ", tempDistanceList distance " + k + " = " + tempDistanceList.get(k));
				if (minDistance > tempDistanceList.get(k)) minDistance = tempDistanceList.get(k);
			}
			//System.out.println("Point " + i + ", minDistance " + minDistance);
			
			//tempRoadCell[2] = (int) Math.ceil(minDistance);// ! change back //h
			tempRoadCell[2] = (int) Math.ceil(minDistance/10);
			//tempRoadCell[2] = (int) Math.ceil(minDistance/30);// the actual cost is the vector number. it should be larger than the multiple
			//System.out.println("Point " + i + ", h  = " + tempRoadCell[2]);
			_roadCells.set(i, tempRoadCell);			
		}
		
		return _roadCells;
	}
	
	public ArrayList<int[]> getNewMVList(int[] _point) //xk, yk, hk, ik-1, jk-1 -> xk, yk, hk, ik, jk
	{// this method is too fussy!!!! read my new method for generating 9 MVs. see "new MVs. good design."
		ArrayList<int[]> newMVList = new ArrayList<int[]>();//9 new moving Vectors
		int maxSpeed = 30;//! B
		//int maxSpeed = 3;//h
		int[] tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3] - 1; //Mk i;
		tempArray[4] = _point[4] - 1;	//Mk j;	
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3] - 1;
		tempArray[4] = _point[4];
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3] - 1;
		tempArray[4] = _point[4] + 1;
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;		
		tempArray[2] = -100; 
		tempArray[3] = _point[3];
		tempArray[4] = _point[4] - 1;
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3];
		tempArray[4] = _point[4];
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3];
		tempArray[4] = _point[4] + 1;
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;
		tempArray[2] = -100; 
		tempArray[3] = _point[3] + 1;
		tempArray[4] = _point[4] - 1;
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3] + 1;
		tempArray[4] = _point[4];
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3] + 1;
		tempArray[4] = _point[4] + 1;
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		return newMVList;
	}
	/*
	public ArrayList<int[]> getNewMVList(int[] _point) //xk, yk, hk, ik-1, jk-1 -> xk, yk, hk, ik, jk
	{
		ArrayList<int[]> newMVList = new ArrayList<int[]>();//9 new moving Vectors
		int maxSpeed = 30;//h
		//int maxSpeed = 3;//h
		int[] tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3] - 1; //Mk i;
		tempArray[4] = _point[4] - 1;	//Mk j;	
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3] - 1;
		tempArray[4] = _point[4];
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3] - 1;
		tempArray[4] = _point[4] + 1;
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;		
		tempArray[2] = -100; 
		tempArray[3] = _point[3];
		tempArray[4] = _point[4] - 1;
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3];
		tempArray[4] = _point[4];
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3];
		tempArray[4] = _point[4] + 1;
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;
		tempArray[2] = -100; 
		tempArray[3] = _point[3] + 1;
		tempArray[4] = _point[4] - 1;
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3] + 1;
		tempArray[4] = _point[4];
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		tempArray = new int[5];		
		tempArray[0] = -1; //Pk x;
		tempArray[1] = -1; //Pk y;	
		tempArray[2] = -100; 
		tempArray[3] = _point[3] + 1;
		tempArray[4] = _point[4] + 1;
		if(Math.abs(tempArray[3]) > maxSpeed) 
		{
			if(tempArray[3] > 0) tempArray[3] = maxSpeed;
			else tempArray[3] = -maxSpeed;
		}
		if(Math.abs(tempArray[4]) > maxSpeed) 
		{
			if(tempArray[4] > 0) tempArray[4] = maxSpeed;
			else tempArray[4] = -maxSpeed;
		}			
		newMVList.add(tempArray);
		
		return newMVList;
	}
	*/
	public ArrayList<int[]> goToNextPoints(ArrayList<int[]> _currentPointsList, int[][] _originalPoints, ArrayList<int[]> _finishPointsList)//A/B
	{
		ArrayList<int[]> newMVList = new ArrayList<int[]>();
		ArrayList<int[]> nextPointsList = new ArrayList<int[]>();
		int[] tempMV = new int[5];
		int[] tempCurrentPoint = new int[5];
		
		Vector<int[]> tempVector = new Vector<int[]>();
		int[] breakdownStep = new int[2];
		boolean needToAdd;
		//1.for each point in _currentPointsList, do the following:
		for(int i = 0; i < _currentPointsList.size(); i++)
		{
			
			newMVList = getNewMVList(_currentPointsList.get(i));
			
			//2.for each new MV of a current point, do the following:
			for(int j = 0; j < newMVList.size(); j++)//9 times
			{
				int[] tempNextPoint = new int[5];
				needToAdd = true;
				tempCurrentPoint = _currentPointsList.get(i).clone();//xk yk
				tempMV = newMVList.get(j).clone();	
				//System.out.println("MV: " + j + ": " + tempMV[0] + " " + tempMV[1] + " " + tempMV[2] + " " + tempMV[3] + " " + tempMV[4]);
				tempVector = breakTheMovementVector(tempMV[3],tempMV[4]);
				//System.out.println("tempVector.size " + tempVector.size());
				if(tempVector.size() == 0)
				{
					//System.out.println("MV: " + j + ", 0,0 not move, no need to add.");
					needToAdd = false;
					continue;
				}
				
		
				//3.for each breakdown steps, do the following:
				for(int k = 0; k < tempVector.size(); k++)
				{					
					breakdownStep = tempVector.get(k).clone();
					//System.out.println("MV: " + j + ", tempCurrentPoint[0] " + tempCurrentPoint[0] + ", tempCurrentPoint[1] " + tempCurrentPoint[1] );
					//System.out.println("MV: " + j + ", breakdownStep[0]: " + breakdownStep[0] + ", breakdownStep[1]: " + breakdownStep[1]);
					
					tempNextPoint[0] = tempCurrentPoint[0] + breakdownStep[0];//x(k+1)
					tempNextPoint[1] = tempCurrentPoint[1] + breakdownStep[1];//y(k+1)
					//System.out.println("MV: " + j + " tempNextPoint[0] " + tempNextPoint[0] + ", tempNextPoint[1] " + tempNextPoint[1]);
					if(tempNextPoint[0] < 0 || tempNextPoint[1] < 0 || tempNextPoint[1] > (_originalPoints.length - 1) || tempNextPoint[0] > (_originalPoints[0].length - 1)) 
					{
						//System.out.println("MV: " + j + " tempNextPoint[0] " + tempNextPoint[0] + ", tempNextPoint[1] " + tempNextPoint[1]);
						//System.out.println("MV: " + j + " MV go off picture! Invalid Moving vector");
						needToAdd = false;
						break;	
					}
						
					if(_originalPoints[tempNextPoint[1]][tempNextPoint[0]] == -1)// attention! here [1] get the i row of _originalPoints = y
					{
						//System.out.println("MV: " + j + " tempNextPoint[0] " + tempNextPoint[0] + ", tempNextPoint[1] " + tempNextPoint[1]);
						//System.out.println("MV: " + j + " MV go off road! Invalid Moving vector");
						needToAdd = false;
						break;
					}
					tempCurrentPoint = tempNextPoint.clone();
				}
				
				//4.check if this point has already been visited before, if already in the array, choose the slower one
				for(int k = 0; k < nextPointsList.size(); k++)
				{
					int[] testArray = nextPointsList.get(k);
					if((tempCurrentPoint[0] == testArray[0]) && (tempCurrentPoint[1] == testArray[1]))
					{
						//if speed of temp < test, choose temp, so delete test,
						if(Math.max(tempCurrentPoint[3], tempCurrentPoint[4]) < Math.max(testArray[3], testArray[4]))
						{
							nextPointsList.remove(k);//						
						}
						else needToAdd = false;
					}
					
				}
				
				if(needToAdd == true)
				{					
					tempNextPoint[3] = tempMV[3];//update the moving vector to i(k),j(k)
					tempNextPoint[4] = tempMV[4];//update the moving vector to i(k),j(k)
					//System.out.println("MV: " + j + " valid");
					nextPointsList.add(tempNextPoint);
				}				
			}			
		}	
		
		nextPointsList = heuristic(nextPointsList, _finishPointsList);//update the h to k+1
		// sort the nextPointsList by ascending order of h = nextPoint[2]
		ArrayList<int[]> sortedNextPointsList = new ArrayList<int[]>();				
		int originalListSize = nextPointsList.size();
		for(int i = 0; i < originalListSize; i++)
		{
			//System.out.println("OriginaSize = " + originalListSize);
			//System.out.println("CurrentSize = " + nextPointsList.size());
			int[] minHPoint = new int[5];
			minHPoint = nextPointsList.get(0).clone();//store
			int[] tempPoint = new int[5];
			int minPointIndex = 0;
			for(int j = 1; j < nextPointsList.size(); j++)
			{
				
				tempPoint = nextPointsList.get(j);//read
				if(minHPoint[2] > tempPoint[2]) 
				{
					minHPoint = nextPointsList.get(j).clone();
					minPointIndex = j;					
				}					
			}
			nextPointsList.remove(minPointIndex);			
			//System.out.println("minH = " + minHPoint[2]);
			sortedNextPointsList.add(minHPoint);
		}
		
		return sortedNextPointsList;
	}
	
	public Vector<int[]> breakTheMovementVector(int i,int j)//A/B
	{
		Vector<int[]> result=new Vector<int[]>();
		int signOfI;
		int signOfJ;
		double ii=new Double(Math.abs(i));
		double jj=new Double(Math.abs(j));
		if(i==0 && j==0)
			return result;
		if(i>0) signOfI=1; else signOfI=-1;
		if(j>0) signOfJ=1; else signOfJ=-1;
		if (j==0){
			for (int f=0;f<ii;f++){
				int[] point={signOfI,0};
				result.add(point);
			}
			return result;
		}
		if (i==0){
			for (int f=0;f<jj;f++){
				int[] point={0,signOfJ};
				result.add(point);
			}
			return result;
		}
		Double a=1.0;
		Double b=1.0;
		double cross=((ii/jj)*(a-.5)+.5);
		while (b<=ii || a<=jj){
			if (b>cross){
				int[] point={0,signOfJ};
				result.add(point);
				a++;
				cross=((ii/jj)*(a-.5)+.5);
			}
			else if (b==cross){
				int[] point={signOfI,signOfJ};
				result.add(point);
				a++;
				b++;
				cross=((ii/jj)*(a-.5)+.5);
			}
			else if (b<cross){
				int[] point={signOfI,0};
				result.add(point);
				b++;
			}
		}
			return result;
	}
	
	public ArrayList<ArrayList<int[]>> addToPathListOfList_B(ArrayList<int[]> _nextPointsList, ArrayList<ArrayList<int[]>> _pathListOfList, int _k)//B
	{
		ArrayList<ArrayList<int[]>> newPathListOfList = new ArrayList<ArrayList<int[]>>();
		
		//for each points in nextPointsList, do the following, until k points add to PathListOfList
		int addPoints = 0;
		boolean finishRun = false;
		for(int i = 0; ((i < _nextPointsList.size()) && (addPoints < _k) && (finishRun == false)); i++)
		{
			boolean addable = true;
			int[] tempNextPoint = new int[5];
			tempNextPoint = _nextPointsList.get(i).clone();//maybe store into newpath, so new.
			//get pathList out from PathListOfList one by one,
			ArrayList<int[]> tempArrayList = null;//read value, reference ok.
			int[] tempArray = null;
			for(int j = 0; j < _pathListOfList.size(); j++)
			{
				addable = true;// make the next point addable for every path list in listOfList
				tempArrayList = _pathListOfList.get(j);
				tempArray = tempArrayList.get(tempArrayList.size() - 1);//read value, reference ok. last point of list
				//System.out.println("addTo method: tempArray[0] " + tempArray[0] + ", tempArray[1] " + tempArray[1] + ", tempArray[2] " + tempArray[2] + ", tempArray[3] " + tempArray[3] + ", tempArray[4] " + tempArray[4]);
				if((tempArray[0] == (tempNextPoint[0] - tempNextPoint[3])) && (tempArray[1] == (tempNextPoint[1] - tempNextPoint[4])))// append to its parent
				{
					//System.out.println("addTo method: match parent point " + tempArray[0] + " " + tempArray[1]);
					// see whether next points is already in path list, avoid loop
					for(int m = 0; m < tempArrayList.size(); m++)
					{
						tempArray = tempArrayList.get(m);
						if((tempArray[0] == tempNextPoint[0]) && (tempArray[1] == tempNextPoint[1]))
						{
							//System.out.println("addTo method: repeat point, not add!");
							addable = false;
							break;
						}
					}
					//parent match and no repeat, add: copy list, add to list, add list to listOfList
					if(addable == true)
					{
						ArrayList<int[]> newPathList = new ArrayList<int[]>();
						newPathList = (ArrayList<int[]>) _pathListOfList.get(j).clone();
						newPathList.add(tempNextPoint);
						newPathListOfList.add(newPathList);
						addPoints++;
						if(tempNextPoint[2] == 0) 
						{
							finishRun = true;
							//System.out.println("addTo method: Get to the finish cell!");
						}
							
						break;//after add to pathlist, break, select the following next point to test
					}					
				}
			}
		}
		
		return newPathListOfList;
	}
	
	public void writeOutputFile(ArrayList<ArrayList<int[]>>_PathListOfList, BufferedWriter _BW, int _numOfExpPoints, long _searchTime)
	{
		try {
			ArrayList<int[]> tempList = new ArrayList<int[]>();
			int[] tempArray = new int[5];
			int[] tempArray2 = new int[5];
			int speed = 0;
			int speedSum = 0;
			int steps = 0;
			//find the List which last point h == 0
			for(int i = 0; i < _PathListOfList.size(); i++)
			{
				tempList = (ArrayList<int[]>) _PathListOfList.get(i).clone();
				tempArray = tempList.get(tempList.size() - 1).clone();
				if(tempArray[2] == 0)
				{
					break;
				}
			}
			//now the path in tempList will go to finishline
			for(int i = 0; i < tempList.size(); i++)
			{				
				tempArray = tempList.get(i);
				if(i == 0)
				{					
					tempArray2 = tempList.get(1);
					speed = Math.max(Math.abs(tempArray2[3]), Math.abs(tempArray2[4]));
					_BW.write(" Step " + i + " {P: (" + tempArray[0] + "," + tempArray[1] + ")         M:(" + tempArray2[3] + "," + tempArray2[4] + ")       " +
							"g=" + i + "    h=" + tempArray2[2] + "    f=" + tempArray2[2] + "   Speed=" + speed + "}\n");
				}
				else if((i + 1) < tempList.size())
				{
					speed = Math.max(Math.abs(tempArray2[3]), Math.abs(tempArray2[4]));
					speedSum += speed;
					tempArray2 = tempList.get(i + 1);
					_BW.write(" Step " + i + " {P: (" + tempArray[0] + "," + tempArray[1] + ")         M:(" + tempArray2[3] + "," + tempArray2[4] + ")       " +
							  "g=" + i + "    h=" + tempArray[2] + "    f=" + (i + tempArray[2]) + "   Speed=" + speed + "}\n");
				
				}
				else//last point, m = 0 = speed
				{					
					_BW.write(" Step " + i + " {P: (" + tempArray[0] + "," + tempArray[1] + ")         M:(0,0)       " +
							  "g=" + i + "    h=0     f=" + i + "   Speed=0}\n");
				}
				steps++;
			}
			//_BW.write("Speed sum=" + speedSum);
			_BW.write("Average Speed=" + speedSum/steps + "\n");
			_BW.write("Number of Steps=" + steps + "\n");
			_BW.write("Number of Explored Nodes=" + _numOfExpPoints + "\n");
			_BW.write("Search Time = " + _searchTime + " Sec");

			System.out.println("writeO: Write to file Done!");
			//_BW.flush();
			//_BW.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	public static void main(String[] args)
	{
		
		String mySearchType = args[0];
		String myInputFile = null;
		String myOutputFile = null;
		
		//start
		SimpleDateFormat sdf = new SimpleDateFormat("MMM d, EEE, yyyy HH:mm:ss.S Z");
		String myBeginSystemTime = sdf.format(new Date()).toString();		
		Date beginTime = null;
		long beginTimeSecond = 0;
		Date endTime = null;
		long endTimeSecond = 0;	
		long searchTime = 0;
		boolean have_alt = false;
		
		try {
			beginTime = sdf.parse(myBeginSystemTime);
			beginTimeSecond = beginTime.getTime();
		} catch (ParseException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			System.exit(-1);
		}		
		
		int myK = 10;//! //h
		if (mySearchType.equals("B"))
		{
			if (args[1].equals("-k"))
			{
				myK = Integer.parseInt(args[2]);
				myInputFile = args[4];
				myOutputFile = args[6];	
				System.out.println("-- Beam search --");
			}
			else
			{
				myK = 10;
				myInputFile = args[2];
				myOutputFile = args[4];
			}
		}
		else if (mySearchType.equals("A"))
		{
			myInputFile = args[2];
			myOutputFile = args[4];
			if (args.length == 6)
				have_alt = true;
			System.out.println("-- A* search --");
		}
		else
		{
			System.out.println("first parameter must be either A or B.");
			System.exit(-1);
		}
		
		Search mySearch = new Search();// new a Search object. //A/B//often
		int myWidth;
		int myHeight;		
		int[][]originalCells = null; // original cells.	
		
		originalCells = mySearch.readFile(myInputFile);//A/B
		myHeight = originalCells.length;
		myWidth = originalCells[0].length;		
		System.out.println("main: myWidth = " + myWidth + ", myHeight = " + myHeight);
		//mySearch.writePoints(myWidth, myHeight, originalCells);
		
		int[] startCell = {-1, -1, -100, 0, 0}; //2 //A/B
		ArrayList<int[]> alterStartCells = new ArrayList<int[]>(); //3, x,y
		ArrayList<int[]> roadCells = new ArrayList<int[]>(); //1,  x,y
		ArrayList<int[]> offRoadCells = new ArrayList<int[]>(); //-1, x,y
		ArrayList<int[]> finishCells = new ArrayList<int[]>(); //4,  x,y
		ArrayList<int[]> myCurrentPointsList = new ArrayList<int[]>();//xk,yk,hk,ik-1,jk-1
		ArrayList<int[]> myNextPointsList = new ArrayList<int[]>();//xk+1,yk+1,hk+1,ik,jk  
		int[] size2Array1 = new int[2];
		//int[] size2Array2 = new int[2];
		//int[] size3Array = new int[3]; //x,y,h
		int numOfExpPoints = 0;
		
		
		
		//A/B
		try{
			FileWriter myFileWriter = new FileWriter(myOutputFile);
			BufferedWriter myBW = new BufferedWriter(myFileWriter);		
			//add original points to ArrayLists.//A/B
			for(int i = 0; i < myHeight; i++) // In the future, I should write this part as a method, use each array as a formal parameter;
			{
				for(int j = 0; j < myWidth; j++)
				{
					switch(originalCells[i][j])
					{
						case -1: 
							size2Array1 = new int[2];
							size2Array1[0] = j;
							size2Array1[1] = i;
							//System.out.println("offRoad i = " + i + ", j = " + j);
							offRoadCells.add(size2Array1);
							break;
						case  1:						
							//size3Array[0] = i;
							//size3Array[1] = j;
							//size3Array[2] = -1;
							size2Array1 = new int[2];
							size2Array1[0] = j;
							size2Array1[1] = i;
							roadCells.add(size2Array1);						
							//System.out.println("roadCell i = " + i + ", j = " + j);
							break;
						case  2:
							startCell[0] = j;
							startCell[1] = i;
							//System.out.println("startPoint i = " + i + ", j = " + j);
							break;
						case  3:
							size2Array1 = new int[2];
							size2Array1[0] = j;
							size2Array1[1] = i;
							alterStartCells.add(size2Array1);
							//System.out.println("alterStartCells i = " + i + ", j = " + j);
							break;
						case  4:
							size2Array1 = new int[2];
							size2Array1[0] = j;
							size2Array1[1] = i;
							finishCells.add(size2Array1);
							//System.out.println("finishCells i = " + i + ", j = " + j);
							break;
						default:
							break;
						
					}
				}
			}
			
			if((startCell[0] == -1))
			{
				System.out.println("Error! There is no start cell!");
				System.exit(-1);
			}
			
			if(roadCells.size() == 0)
			{
				System.out.println("Error! There is no road cell!");
				System.exit(-2);
			}
			
			if(finishCells.size() == 0)
			{
				System.out.println("Error! There is no finish cell!");
				System.exit(-3);
			}
			
			
			/*
			size2Array1 = new int[2];			
			Iterator<int[]> i = roadCells.iterator();
			while(i.hasNext())
			{
				size2Array1 = (int[]) i.next();
				myBW.write("roadCells = " + size2Array1[0] + ", " + size2Array1[1] + "\n");
			}
			*/
			//myBW.write("roadCells length: " + roadCells.size() + "\n\n");
			/*
			size2Array1 = new int[2];
			for(int j = 0; j < (finishCells.size()); j++)
			{
				size2Array1 = finishCells.get(j).clone();
				myBW.write("FinishCells " + size2Array1[0] + ", " + size2Array1[1] + "\n");
			}
			//myBW.write("FinishCells length: " + finishCells.size() + "\n\n");
			/*
			
			//System.out.println("roadCells = " + myRoadCell[0] + ", " + myRoadCell[1] + ", " + myRoadCell[2]);
			/*
			myRoadCell = roadCells.get(0);
			System.out.println("get0 roadCells = " + myRoadCell[0] + ", " + myRoadCell[1] + ", " + myRoadCell[2]);
			myRoadCell = roadCells.get(1);
			System.out.println("get1 roadCells = " + myRoadCell[0] + ", " + myRoadCell[1] + ", " + myRoadCell[2]);
			myRoadCell = roadCells.get(2);
			System.out.println("get2 roadCells = " + myRoadCell[0] + ", " + myRoadCell[1] + ", " + myRoadCell[2]);
			*/
						
			
			if (mySearchType.equals("B"))
			{
				//Beam Search
				//add startCell to current 
				//System.out.println("main: startCell = " + startCell[0] + " " + startCell[1] + " " + startCell[2] + " " + startCell[3] + " " + startCell[4] );
				myCurrentPointsList.add(startCell); 
				ArrayList<int[]> myPathList = new ArrayList<int[]>(); 
				myPathList.add(startCell);
				
				//add first path to ListOfList //B
				ArrayList<ArrayList<int[]>> myPathListOfList = new ArrayList<ArrayList<int[]>>(); //xk+1,yk+1,hk+1,ik,jk
				myPathListOfList.add(myPathList);
				//System.out.println("main: myPathListOfList.size = " + myPathListOfList.size()); //A/B
							
				//print current points.B
				int[] tempArray;
				
				for(int j = 0; j < myCurrentPointsList.size(); j++)
				{
					tempArray = myCurrentPointsList.get(j);// only for print, reference is fine.				
					System.out.println("main: myCurrPointsLists " + j + " = " + tempArray[0] + " " + tempArray[1] + " " + tempArray[2] + " " + tempArray[3] + " " + tempArray[4]);				
				}
				
				
				myNextPointsList = mySearch.goToNextPoints(myCurrentPointsList, originalCells, finishCells);//A/B//,
				
				//print next points.
				/*
				for(int j = 0; j < myNextPointsList.size(); j++)
				{
					tempArray = myNextPointsList.get(j);// only for print, reference is fine.				
					System.out.println("main: myNextPointsLists " + j + " = " + tempArray[0] + " " + tempArray[1] + " " + tempArray[2] + " " + tempArray[3] + " " + tempArray[4]);				
				}
				*/			
				myPathListOfList = mySearch.addToPathListOfList_B(myNextPointsList, myPathListOfList, myK);
				
				//System.out.println("main: myPathListOfList size " + myPathListOfList.size());			
				
				boolean myFinishRun = false;
				while(myFinishRun == false)
				{
					//check finish
					int[] testArray = null;
					ArrayList<int[]> testList = null;
					//System.out.println("main: myPathListOfList.size() " + myPathListOfList.size());
					if(myPathListOfList.size() == 0)
					{
						System.out.println("main: Can not go to finishline, maybe change k will help.");
						break;
					}
					for(int j = 0; j < myPathListOfList.size();j++)
					{
						testList = myPathListOfList.get(j);
						testArray = testList.get(testList.size() - 1);
						//System.out.println("main: last point h of pathList " + j + " = " + testArray[2]);
						if(testArray[2] == 0)// h = 0, terminate
						{
							myFinishRun = true;
							break;
						}
					}
					
					if(myFinishRun == false)//pause
					{
						myCurrentPointsList = new ArrayList<int[]>();
						//get current points from listOfList
						for(int j = 0; j < myPathListOfList.size();j++)
						{
							ArrayList<int[]> tempCurrentList = new ArrayList<int[]>();
							int[] tempCurrentArray = new int[5];
							tempCurrentList = (ArrayList<int[]>) myPathListOfList.get(j).clone();
							tempCurrentArray = tempCurrentList.get(tempCurrentList.size() - 1).clone();// last element of pathList is my current point						
							myCurrentPointsList.add(tempCurrentArray);
							numOfExpPoints++;
						}										
						
						//myCurrentPointsList = (ArrayList<int[]>) myNextPointsList.clone();// logic error, current point is the listOfList last element
										
						myNextPointsList = new ArrayList<int[]>();
						myNextPointsList = mySearch.goToNextPoints(myCurrentPointsList, originalCells, finishCells);
						//myPathListOfList = new ArrayList<ArrayList<int[]>>();
						myPathListOfList = mySearch.addToPathListOfList_B(myNextPointsList, myPathListOfList, myK);
						//print current points.
						for(int j = 0; j < myCurrentPointsList.size(); j++)
						{
							tempArray = myCurrentPointsList.get(j);// only for print, reference is fine.				
							System.out.println("main: myCurrentPointsLists " + j + " = " + tempArray[0] + " " + tempArray[1] + " " + tempArray[2] + " " + tempArray[3] + " " + tempArray[4]);				
						}
						/*
						//print next points.
						for(int j = 0; j < myNextPointsList.size(); j++)
						{
							tempArray = myNextPointsList.get(j);// only for print, reference is fine.				
							System.out.println("main: myNextPointsLists " + j + " = " + tempArray[0] + " " + tempArray[1] + " " + tempArray[2] + " " + tempArray[3] + " " + tempArray[4]);				
						}
						*/
					}
									
				}
				
				if(myFinishRun == true)
				{
					// end time		
					String myEndSystemTime = sdf.format(new Date()).toString();
					try {
						endTime = sdf.parse(myEndSystemTime);
						endTimeSecond = endTime.getTime();
					} catch (ParseException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
						System.exit(-1);
					}	
					
					searchTime = (endTimeSecond - beginTimeSecond)/1000;
					
					
					System.out.println("main: We finish!");						
					mySearch.writeOutputFile(myPathListOfList, myBW, numOfExpPoints++, searchTime);										
				}
				else
				{
					System.out.println("main: We cannot finish!");	
					myBW.write("Cannot finish");
				}
			}
			
			if (mySearchType.equals("A"))
			{
				treeNode myRoot = new treeNode();
				myRoot.root = true;
				//myRoot.point = startCell;
				myRoot.x = startCell[0];
				myRoot.y = startCell[1];
				myRoot.vector_i =0;
				myRoot.vector_j = 0;
				myRoot.g = 0;
				myRoot.altRoot = false;
				double distance = Math.sqrt(Math.pow((startCell[0] - finishCells.get(0)[0]), 2) + Math.pow((startCell[1] - finishCells.get(0)[1]), 2));
				int H = (int) Math.ceil(distance);//!
				myRoot.h = H;
				long id = (startCell[1]*mySearch.factor+startCell[0])*10000 + myRoot.vector_i*100 + myRoot.vector_j;
				mySearch.nodesInTree.add(id);
				
				//System.out.println("node added to nodesInTree:"+startCell[0]+","+startCell[1]+", "+(startCell[1]*mySearch.factor + startCell[0]));
				SortedMap<Integer, Set> myFringe = new TreeMap();//<f, points with the same f>
				Set startPoint = new HashSet();
				startPoint.add(myRoot);
				myFringe.put(myRoot.g+myRoot.h, startPoint);
				
				if(have_alt){
					Iterator it = alterStartCells.iterator();
					while(it.hasNext()){
						int[] ords = (int[])it.next();
						treeNode altRoot = new treeNode();
						altRoot.root = true;
						//myRoot.point = startCell;
						altRoot.x = ords[0];
						altRoot.y = ords[1];
						altRoot.vector_i =0;
						altRoot.vector_j = 0;
						altRoot.g = 0;
						altRoot.altRoot = true;
						distance = Math.sqrt(Math.pow((ords[0] - finishCells.get(0)[0]), 2) + Math.pow((ords[1] - finishCells.get(0)[1]), 2));
						H = (int) Math.ceil(distance);//!
						altRoot.h = H;
						id = (ords[1]*mySearch.factor+ords[0])*10000 + altRoot.vector_i*100 + altRoot.vector_j;
						mySearch.nodesInTree.add(id);
						if(myFringe.containsKey(altRoot.h)){
							myFringe.get(altRoot.h).add(altRoot);
						}else{
							Set newSet = new HashSet();
							newSet.add(altRoot);
							myFringe.put(altRoot.h, newSet);
						}
					}
					
				}
				//myFringe.put(0, startPoint);
				treeNode finishPoint = null;
				
				//System.out.println("factor:"+mySearch.factor);
				Date Astart = new Date();
				int maxFringeSize = 0;
				while(finishPoint == null){
					int size = 0;
					for(Map.Entry<Integer, Set> entry: myFringe.entrySet()){
						size += entry.getValue().size();						
					}
					if(size>maxFringeSize)
						maxFringeSize = size;
//					
//					if(count%10000==0)
//						System.out.println(""+count);
					count++;
					finishPoint = mySearch.aStarSearch(myFringe, originalCells, finishCells);
					
				}
				Date Aend = new Date();
				System.out.println("maxFringeSize: "+maxFringeSize+"  \ntime used: "+(Aend.getTime()-Astart.getTime()));
				
				System.out.println("search finished");
				boolean finish = false;
				int step_count = 0;
				ArrayList<treeNode> myPathList = new ArrayList<treeNode>();
				while(finishPoint != null){
					myPathList.add(finishPoint);
					System.out.println("step "+step_count+": ("+finishPoint.x+","+finishPoint.y+")");
					step_count++;
					if(finishPoint.altRoot == true)
						System.out.println("start from alt root");
					finishPoint = finishPoint.parent;
				}
				
				int size = myPathList.size();
				int total_speed = 0;
				for(int i=0; i<size; i++){
					treeNode cur = myPathList.get(size-1-i);
					String msg = "Step "+i+" {P: ("+cur.x+","+cur.y+") M:("+cur.vector_i+","+cur.vector_j+") ";
					int speed = Math.max(Math.abs(cur.vector_i), Math.abs(cur.vector_j));
					total_speed += speed;
					msg += "g="+cur.g+" h="+cur.h+" f="+(cur.g+cur.h)+" speed:"+speed+"}";
					myBW.append(msg);
					myBW.newLine();
				}
				myBW.write("Average Speed= "+((float)total_speed/size));
				myBW.newLine();
				myBW.write("Number Of Steps= "+size);
				myBW.newLine();
				myBW.write("Number Of Explored Nodes= "+count);
				myBW.newLine();
				myBW.write("Search Time= "+(Aend.getTime()-Astart.getTime())/1000+" sec");
				myBW.newLine();
				
			}
			
			
			
			
			
			myBW.flush();
			myBW.close();
			//System.out.println("main: write to file.");
		
		} catch (IOException e) {
			System.out.println(e);
		}
		
	}//main
	
	static int count =0;
	public int factor = 1;
	public Set nodesInTree = new HashSet(); 
	public treeNode aStarSearch(SortedMap<Integer, Set> myFringe, int[][] _originalCells, ArrayList<int[]> _finishCells){
		int key = myFringe.firstKey();
		//System.out.println("first key:"+key);
		Set nodesToExpand = myFringe.get(myFringe.firstKey());
		Iterator it = nodesToExpand.iterator();
		treeNode selectedNode = (treeNode)it.next();
		int x = selectedNode.x;
		int y = selectedNode.y;
		
		//if(count%10000 == 0){
			System.out.println("A*: x = " + x + " y = " + y + " g = "+selectedNode.g);//,
			System.out.println("A*: i = " + selectedNode.vector_i + " j = " + selectedNode.vector_j);
		//}
		it.remove();
		if(!it.hasNext()){
			myFringe.remove(myFringe.firstKey());
		}
		
		Object[] generatedNodes = getNewNodeList(selectedNode, _originalCells);
		for(int i=0; i<generatedNodes.length; i++){
			treeNode currentChild = (treeNode)generatedNodes[i];
			selectedNode.addChild(currentChild);//add tree
			int minH = 9999999;
			int[] tempRoadCell = new int[]{currentChild.x, currentChild.y};
			Iterator it2 = _finishCells.iterator();
			while(it2.hasNext()){
				int[] finishCell = (int[])it2.next();
				double distance = Math.sqrt(Math.pow((tempRoadCell[0] - finishCell[0]), 2) + Math.pow((tempRoadCell[1] - finishCell[1]), 2));
				int H = (int) Math.ceil(distance);//! heuristic
				
				if(H<minH)
					minH = H;
			}
			currentChild.h = minH;
			
			if(minH == 0)
				return currentChild;
			
			int f = minH+currentChild.g;
			if(myFringe.containsKey(f)){
				myFringe.get(f).add(currentChild);
			}else{
				Set cells = new HashSet();
				cells.add(currentChild);
				myFringe.put(f, cells);
			}
			long id = (tempRoadCell[1]*factor+tempRoadCell[0])*10000 + currentChild.vector_i*100 + currentChild.vector_j;
			nodesInTree.add(id);
			//System.out.println("node added to nodesInTree:"+tempRoadCell[0]+","+tempRoadCell[1]+", "+(tempRoadCell[1]*factor + tempRoadCell[0]));
			
		}//for(int i=0; i<generatedNodes.length; i++)
		return null;		
	}
	// new MVs. good design.
	public int[][] vectorDiff = new int[][]{{-1,-1}, {0, -1}, {1, -1},
											{-1, 0}, {0, 0}, {1, 0},
											{-1, 1}, {0, 1}, {1,1}};
	public int[][] leastG;
	public Object[] getNewNodeList(treeNode current, int[][] _originalCells){
		int x = current.x;
		int y = current.y;
		int vector_i = current.vector_i;
		int vector_j = current.vector_j;
		int maxSpeed = 30;//! A
		Vector<treeNode> newNodes = new Vector();
		
		for(int i=0; i<vectorDiff.length; i++){
			int newVector_i = vector_i + vectorDiff[i][0];
			int newVector_j = vector_j + vectorDiff[i][1];
			if(Math.abs(newVector_i) > maxSpeed) 
			{
				if(newVector_i < 0) newVector_i = -maxSpeed;
				else newVector_i = maxSpeed;
			}
			if(Math.abs(newVector_j) > maxSpeed) 
			{
				if(newVector_j < 0) newVector_j = -maxSpeed;
				else newVector_j = maxSpeed;
			}
			
			int nextX = x + newVector_i;
			if(nextX<0 || nextX>= _originalCells[0].length)
				continue;
			int nextY = y + newVector_j;
			if(nextY<0 || nextY>= _originalCells.length)
				continue;
			if(_originalCells[nextY][nextX]== -1)
				continue;
			
			Vector<int[]> breakDownVectors = breakTheMovementVector(newVector_i, newVector_j);
			Iterator it = breakDownVectors.iterator();
			boolean valid = true;
			int[] currentNode = new int[]{x, y};
			while(it.hasNext()){
				int[] step = (int[])it.next();
				currentNode[0] += step[0];
				currentNode[1] += step[1];
//				if(currentNode[0]<0 || currentNode[0]>= _originalCells[0].length){
//					valid = false;
//					break;
//				}
//				if(currentNode[1]<0 || currentNode[1]>= _originalCells.length){
//					valid = false;
//					break;
//				}
				if(_originalCells[currentNode[1]][currentNode[0]]== -1){
					valid = false;
					break;
				}
			}//while(it.hasNext())
			
			int newX = x + newVector_i;
			int newY = y + newVector_j;
			//
			treeNode checkPathNode = current;
			while(checkPathNode != null){
				if(newX==checkPathNode.x && newY==checkPathNode.y){
					valid = false;
					break;
				}
				checkPathNode = checkPathNode.parent;
			}
			
//			int currentG = current.g + 1;
//			if(leastG[newY][newX] == 0 && valid){
//				leastG[newY][newX] = currentG;
//			}else{
//				if(leastG[newY][newX]<currentG)
//					valid = false;
//			}
			
			long id = (newY*factor+newX)*10000 + newVector_i*100 + newVector_j;
			if(nodesInTree.contains(id)){
//				if(count%10000 == 0)
//					System.out.println("duplicate in nodesInTree: "+id);
				valid = false;
			}
			
			if(valid){
				treeNode child = new treeNode();
				child.x = newX;
				child.y = newY;
				child.vector_i = newVector_i;
				child.vector_j = newVector_j;
				newNodes.add(child);
			}
		}//for(int i=0; i<vectorDiff.length; i++)
		
		return newNodes.toArray();
	}
}
